package io.gitee.wminyu.day03.Sort;


import java.util.Arrays;
import java.util.Scanner;

public class Quick_sort {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int m = input.nextInt();
        int arrays[] = new int[m];
        for (int i = 0; i < m; i++) {
            arrays[i] = input.nextInt();
        }
        System.out.println("原数组为：" + Arrays.toString(arrays));
       Quick(arrays,0,arrays.length-1);
        System.out.println("最终排序为："+Arrays.toString(arrays));
    }
    public static void Quick(int[] numble,int zz,int yy){
        int key,z,y;
        int i  =0;
        if (zz<yy){
            z = zz;
            y = yy;
            key = numble[z];
            do{
                //从右往左寻找首个小于key的元素位置y
                while (z<y&&numble[y]>key){
                    y--;
                };
                if(z<y){
                    numble[z]=numble[y];
                    z++;
                }
                //从左往右寻找首个大于key的元素位置z
                while (z<y&&(numble[z]<key)){
                    z++;
                }
                if (z<y){
                    numble[y] = numble[z];
                    y--;
                }
            }while (z!=y);
             numble[z]= key;
            System.out.print("第"+(++i)+"趟排序为：");
            Display(numble);
            System.out.println();
            //采用递归进行循环
            Quick(numble,zz,z-1);
            Quick(numble,z+1,yy);

        }
    }
    public static void Display(int[] a){
        for (int i=0;i<a.length;i++){
            System.out.print(a[i]+" ");
        }
    }

}
